package demo.letcode.top100;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class _出现频率最高的k个数字 {
    public static void main(String[] args) {
        /*
         * 给定一个整数数组 nums 和一个整数 k ，请返回其中出现频率前k高的元素。可以按 任意顺序 返回答案。
         * 示例 1：
         * 输入: nums = [1,1,1,2,2,3], k = 2
         * 输出: [1,2]
         *
         * 示例 2：
         * 输入: nums = [1], k = 1
         * 输出: [1]
         */
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k=2;
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 2. 使用最小堆来维护前k个高频元素
        // 堆中存储的是数字，按频率从小到大排序
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
                (a, b) -> frequencyMap.get(a) - frequencyMap.get(b)
        );

        for (int num : frequencyMap.keySet()) {
            minHeap.offer(num); // 加入堆
            if (minHeap.size() > k) {
                minHeap.poll(); // 移除频率最小的元素
            }
        }

        // 4. 将堆中的元素转换为数组
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll();
        }
        System.out.println(Arrays.toString(result));
    }
}
